Split a string in balanced strings

Time: O(N); Space: O(1); easy

Balanced strings are those who have equal quantity of ‘L’ and ‘R’ characters.

Given a balanced string s split it in the maximum amount of balanced strings.

Return the maximum amount of splitted balanced strings.

Example 1:

Input: s = “RLRRLLRLRL”

Output: 4

Explanation:

  • s can be split into “RL”, “RRLL”, “RL”, “RL”, each substring contains same number of ‘L’ and ‘R’.

Example 2:

Input: s = “RLLLLRRRLR”

Output: 3

Explanation:

  • s can be split into “RL”, “LLLRRR”, “LR”, each substring contains same number of ‘L’ and ‘R’.

Example 3:

Input: s = “LLLLRRRR”

Output: 1

Explanation:

  • s can be split into “LLLLRRRR”.

Example 4:

Input: s = “RLRRRLLRLL”

Output: 2

Explanation:

  • s can be split into “RL”, “RRRLLRLL”, since each substring contains an equal number of ‘L’ and ‘R’

Constraints:

  • 1 <= len(s) <= 1000

  • s[i] = ‘L’ or ‘R’

Hints:

  1. Loop from left to right maintaining a balance variable when it gets an L increase it by one otherwise decrease it by one.

  2. Whenever the balance variable reaches zero then we increase the answer by one.

[1]:

class Solution1(object):
    """
    Time: O(N)
    Space: O(1)
    """
    def balancedStringSplit(self, s):
        """
        :type s: str
        :rtype: int
        """
        result, count = 0, 0
        for c in s:
            count += 1 if c == 'L' else -1
            if count == 0:
                result += 1
        return result

[3]:

sol = Solution1()
s = "RLRRLLRLRL"
assert sol.balancedStringSplit(s) == 4
s = "RLLLLRRRLR"
assert sol.balancedStringSplit(s) == 3
s = "LLLLRRRR"
assert sol.balancedStringSplit(s) == 1
s = "RLRRRLLRLL"
assert sol.balancedStringSplit(s) == 2